训练指南 UVA - 11383（KM算法的应用 lx+ly >=w(x,y)）

Diposting di | Edited on

Golden Tiger Claw

UVA - 11383

题意

给一个n*n的矩阵，每个格子中有正整数w[i[j]，试为每行和每列分别确定一个数字row[i]和col[i]，使得任意格子w[i][j]<=row[i]+col[j]恒成立。先输row，再输出col，再输出全部总和（总和应尽量小）。

思路

本题与匹配无关，但可以用KM算法解决。

　　KM算法中的顶标就是保持了Lx[i]+ly[j]>=g[i[j]再求最大权和匹配的，但这个最大权和并没有关系。我们可以将row[i]看成一个男的，col[i]看成一个女的，这样男女的总数就相等。

　　一般来说，Lx[i]或Ly[i]仅需要取该行/列中最大的那个数即可保证满足要求，但是这样太大了，可以通过调整来使得总和更小。而KM算法的过程就是一个调整的过程，每一对匹配的男女的那条边的权值就会满足等号 wi[j]=row[i]+col[j]，至少需要一个来满足等号，这样才能保证row[i]+col[j]是达到最小的，即从j列看，col[j]满足条件且最小，从i行看，row[i]满足条件且最小。这刚好与KM算法求最大权和一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=5e2+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
int g[530][530];  ///存图
int nx,ny; /// 两边点数
bool visx[maxn],visy[maxn];
int slack[maxn];
int linker[maxn];   ///y中各点匹配状态
int lx[maxn],ly[maxn]; /// x,y中的点标号
bool dfs(int x){
    visx[x]=true;
    for(int y=0;y<ny;y++){
        if(visy[y])continue;
        int tmp=lx[x]+ly[y]-g[x][y];
        if(tmp==0){
            visy[y]=true;
            if(linker[y]==-1||dfs(linker[y])){
                linker[y]=x;return true;
            }
        }
        else if(slack[y]>tmp)slack[y]=tmp;
    }
    return false;
}
int KM(){
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for(int i=0;i<nx;i++){
        lx[i]=-inf;
        for(int j=0;j<ny;j++){
            if(g[i][j]>lx[i])lx[i]=g[i][j];
        }
    }
    for(int x=0;x<nx;x++){
        for(int i=0;i<ny;i++)slack[i]=inf;
        while(true){
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x))break;
            int d=inf;
            for(int i=0;i<ny;i++)
                if(!visy[i]&&d>slack[i])d=slack[i];
            for(int i=0;i<nx;i++)
                if(visx[i])lx[i]-=d;
            for(int i=0;i<ny;i++)
                if(visy[i])ly[i]+=d;
                else slack[i]-=d;
        }
    }
    int res=0;
    for(int i=0;i<ny;i++)
        if(linker[i]!=-1)res+=g[linker[i]][i];
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    while(cin>>n){
        nx=ny=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)cin>>g[i][j];
        int ans=KM();
        cout<<lx[0];
        for(int i=1;i<n;i++)cout<<" "<<lx[i];cout<<endl;
        cout<<ly[0];
        for(int i=1;i<n;i++)cout<<" "<<ly[i];cout<<endl;
        cout<<ans<<endl;
    }

    return 0;
}